home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Compilers⁄Interps / little-c / Parser.c < prev    next >
Text File  |  1993-10-04  |  12KB  |  496 lines
  1. /* Recursive descent parser for integer expressions
  2.    which may include variables and function calls.  */
  3.  
  4. #include <setjmp.h>
  5. #include <math.h>
  6. #include <ctype.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <stdio.h>
  10.  
  11. #define NUM_FUNC       100
  12. #define NUM_GLOBAL_VARS 100
  13. #define NUM_LOCAL_VARS  200
  14. #define ID_LEN          31 
  15. #define FUNC_CALLS      31
  16. #define PROG_SIZE     10000
  17. #define FOR_NEST    31
  18.  
  19. enum tok_types {DELIMITER, IDENTIFIER, NUMBER, KEYWORD, TEMP,
  20.             STRING, BLOCK};
  21. enum tokens {ARG, CHAR, INT, IF, ELSE, FOR, DO, WHILE, SWITCH,
  22.              RETURN, EOL, FINISHED, END};
  23. enum double_ops {LT=1, LE, GT, GE, EQ, NE};
  24.  
  25. /* These are the constants used to call sntx_err() when
  26.    a syntax error occurs.  Add more if you like.
  27.    NOTE: SYNTAX is a generic error message used when
  28.    nothing else seems appropriate.
  29. */
  30. enum error_msg 
  31.      {SYNTAX, UNBAL_PARENS, NO_EXP, EQUALS_EXPECTED,
  32.       NOT_VAR, PARAM_ERR, SEMI_EXPECTED,
  33.       UNBAL_BRACES, FUNC_UNDEF, TYPE_EXPECTED,
  34.       NEST_FUNC, RET_NOCALL, PAREN_EXPECTED,
  35.       WHILE_EXPECTED, QUOTE_EXPECTED, NOT_TEMP,
  36.       TOO_MANY_LVARS};
  37.  
  38. extern char *prog;  /* current location in source code */
  39. extern char *p_buf;  /* points to start of program buffer */
  40. extern jmp_buf e_buf; /* hold environment for longjmp() */
  41.  
  42. /* An array of these structures will hold the info
  43.    associated with global variables.
  44. */
  45. extern struct variable_type {
  46.   char var_name[32];
  47.   int  var_type;
  48.   int  value;
  49. }  global_vars[NUM_GLOBAL_VARS];
  50.  
  51. /*  This is the function call stack. */
  52. extern struct func_type {
  53.   char func_name[32];
  54.   char *loc;  /* location of function entry point in file */
  55. } func_stack[NUM_FUNC];
  56.  
  57. /* Keyword table */
  58. extern struct commands {
  59.   char command[20];
  60.   char tok;
  61. } table[];
  62.  
  63. /* "Standard library" functions are declared here so
  64.    they can be put into the internal function table that
  65.    follows.
  66. */
  67. int call_getche(void), call_putch(void);
  68. int call_puts(void), print(void), getnum(void);
  69.  
  70. struct intern_func_type {
  71.   char *f_name; /* function name */
  72.   int (* p)();  /* pointer to the function */
  73. } intern_func[] = {
  74.   "getche", call_getche,
  75.   "putch",  call_putch,
  76.   "puts",   call_puts,
  77.   "print",  print,
  78.   "getnum", getnum,
  79.   "", 0  /* null terminate the list */
  80. };
  81.  
  82. extern char token[80];  /* string representation of token */
  83. extern char token_type; /* contains type of token */
  84. extern char tok;        /* internal representation of token */
  85. extern int ret_value;   /* function return value */
  86. void eval_exp(int *value);
  87. void eval_exp0(int *value);
  88. void eval_exp1(int *value);
  89. void eval_exp2(int *value);
  90. void eval_exp3(int *value);
  91. void eval_exp4(int *value);
  92. void eval_exp5(int *value);
  93. void atom(int *value);
  94. void sntx_err(int error), putback(void);
  95. void assign_var(char *var_name, int value);
  96. int  isdelim(char c), look_up(char *s), iswhite(char c);
  97. int  find_var(char *s), get_token(void);
  98. int  internal_func(char *s);
  99. int  is_var(char *s);
  100. char *find_func(char *name);
  101. void call(void);
  102.  
  103. /* Entry point into parser. */
  104. void eval_exp(int *value)
  105. {
  106.   get_token();
  107.   if(!*token) {
  108.     sntx_err(NO_EXP);
  109.     return;
  110.   }
  111.   if(*token==';') {
  112.     *value = 0; /* empty expression */
  113.     return;
  114.   }
  115.   eval_exp0(value);
  116.   putback(); /* return last token read to input stream */
  117. }
  118.  
  119. /* Process an assignment expression */
  120. void eval_exp0(int *value)
  121. { char temp[ID_LEN];  /* holds name of var receiving
  122.              the assignment */
  123.   register int temp_tok;
  124.   if(token_type==IDENTIFIER) {
  125.     if(is_var(token)) {  /* if a var, see if assignment */
  126.       strcpy(temp, token);
  127.       temp_tok = token_type;
  128.       get_token();
  129.       if(*token=='=') {  /* is an assignment */
  130.     get_token();
  131.     eval_exp0(value);  /* get value to assign */
  132.     assign_var(temp, *value);  /* assign the value */
  133.     return;
  134.       }
  135.       else {  /* not an assignment */
  136.     putback();  /* restore original token */
  137.     strcpy(token, temp);
  138.     token_type = temp_tok;
  139.       }
  140.     }
  141.   }
  142.   eval_exp1(value);
  143. }
  144.  
  145. /* This array is used by eval_exp1().  Because
  146.    some compilers cannot initialize an array within a
  147.    function it is defined as a global variable.
  148. */
  149. char relops[7] = {
  150.   LT, LE, GT, GE, EQ, NE, 0
  151. };
  152.  
  153. /* Process relational operators. */
  154. void eval_exp1(int *value)
  155. {
  156.   int partial_value;
  157.   register char op;
  158.   eval_exp2(value);
  159.   op = *token;
  160.   if(strchr(relops, op)) {
  161.     get_token();
  162.     eval_exp2(&partial_value);
  163.     switch(op) {  /* perform the relational operation */
  164.       case LT:
  165.     *value = *value < partial_value;
  166.     break;
  167.       case LE:
  168.     *value = *value <= partial_value;
  169.     break;
  170.       case GT:
  171.     *value = *value > partial_value;
  172.     break;
  173.       case GE:
  174.     *value = *value >= partial_value;
  175.     break;
  176.       case EQ:
  177.     *value = *value == partial_value;
  178.     break;
  179.       case NE:
  180.     *value = *value != partial_value;
  181.      break;
  182.     }
  183.   }
  184. }
  185.  
  186. /*  Add or subtract two terms. */
  187. void eval_exp2(int *value)
  188. {
  189.   register char  op;
  190.   int partial_value;
  191.   eval_exp3(value);
  192.   while((op = *token) == '+' || op == '-') {
  193.     get_token();
  194.     eval_exp3(&partial_value);
  195.     switch(op) {  /* add or subtract */
  196.       case '-':
  197.     *value = *value - partial_value;
  198.     break;
  199.       case '+':
  200.     *value = *value + partial_value;
  201.     break;
  202.     }
  203.   }
  204. }
  205.  
  206. /* Multiply or divide two factors. */
  207. void eval_exp3(int *value)
  208. {
  209.   register char  op;
  210.   int partial_value, t;
  211.   eval_exp4(value);
  212.   while((op = *token) == '*' || op == '/' || op == '%') {
  213.     get_token();
  214.     eval_exp4(&partial_value);
  215.     switch(op) { /* mul, div, or modulus */
  216.       case '*':
  217.     *value = *value * partial_value;
  218.     break;
  219.       case '/':
  220.     *value = (*value) / partial_value;
  221.     break;
  222.       case '%':
  223.     t = (*value) / partial_value;
  224.         *value = *value-(t * partial_value); 
  225.         break; 
  226.     }
  227.   }
  228. }
  229.  
  230. /* Is a unary + or -. */
  231. void eval_exp4(int *value)
  232. {
  233.   register char  op; 
  234.   op = '\0'; 
  235.   if(*token=='+' || *token=='-') {
  236.     op = *token; 
  237.     get_token(); 
  238.   }
  239.   eval_exp5(value); 
  240.   if(op)
  241.     if(op=='-') *value = -(*value); 
  242. }
  243.  
  244. /* Process parenthesized expression. */
  245. void eval_exp5(int *value)
  246. {
  247.   if((*token == '(')) {
  248.     get_token(); 
  249.     eval_exp0(value);   /* get subexpression */
  250.     if(*token != ')') sntx_err(PAREN_EXPECTED); 
  251.     get_token(); 
  252.   }
  253.   else
  254.     atom(value); 
  255. }
  256.  
  257. /* Find value of number, variable or function. */
  258. void atom(int *value)
  259. {
  260.   int i;
  261.   switch(token_type) {
  262.   case IDENTIFIER:
  263.     i = internal_func(token);
  264.     if(i!= -1)                   /* call "standard library" function */
  265.       *value = (*intern_func[i].p)();
  266.     else if(find_func(token)) {  /* call user-defined function */
  267.       call();
  268.       *value = ret_value;
  269.     }
  270.     else
  271.       *value = find_var(token);  /* get var's value */
  272.     get_token();
  273.     return;
  274.   case NUMBER: /* is numeric constant */
  275.     *value = atoi(token);
  276.     get_token();
  277.     return; 
  278.   case DELIMITER: /* see if character constant */
  279.     if(*token=='\'') {
  280.       *value = *prog;
  281.       prog++;
  282.       if(*prog!='\'') sntx_err(QUOTE_EXPECTED);
  283.       prog++;
  284.       get_token();
  285.     }
  286.     return;
  287.   default:
  288.     if(*token==')') return; /* process empty expression */
  289.     else sntx_err(SYNTAX); /* syntax error */
  290.   }
  291. }
  292.  
  293. /* Display an error message. */
  294. void sntx_err(int error)
  295. {
  296.   char *p, *temp;
  297.   int linecount = 0;
  298.   register int i;
  299.   static char *e[]= {   
  300.     "syntax error", 
  301.     "unbalanced parentheses", 
  302.     "no expression present",
  303.     "equals sign expected",
  304.     "not a variable",
  305.     "parameter error",
  306.     "semicolon expected",
  307.     "unbalanced braces",
  308.     "function undefined",
  309.     "type specifier expected",
  310.     "too many nested function calls",
  311.     "return without call",
  312.     "parentheses expected",
  313.     "while expected",
  314.     "closing quote expected",
  315.     "not a string",
  316.     "too many local variables"
  317.   }; 
  318.   printf("%s", e[error]); 
  319.   p = p_buf;
  320.   while(p != prog) {  /* find line number of error */
  321.     p++;
  322.     if(*p == '\r') linecount++;
  323.   }
  324.   printf(" in line %d\n", linecount);
  325.   temp = p;
  326.   for(i=0; i<20 && p>p_buf && *p!='\n'; i++, p--);
  327.   for(i=0; i<30 && p<=temp; i++, p++) printf("%c", *p);
  328.   longjmp(e_buf, 1); /* return to save point */
  329. }
  330.  
  331. /* Get a token. */
  332. get_token(void)
  333. {
  334.   register char *temp;
  335.   token_type = 0;
  336.   tok = 0;
  337.   temp = token;
  338.   *temp = '\0';
  339.   /* skip over white space */
  340.   while(iswhite(*prog) && *prog) ++prog; 
  341.   if(*prog=='\r') { 
  342.     ++prog;
  343.     ++prog;
  344.     /* skip over white space */
  345.     while(iswhite(*prog) && *prog) ++prog;
  346.   }
  347.   if(*prog=='\0') { /* end of file */
  348.     *token = '\0';
  349.     tok = FINISHED;
  350.     return(token_type=DELIMITER);
  351.   }
  352.   if(strchr("{}", *prog)) { /* block delimiters */
  353.     *temp = *prog;
  354.     temp++;
  355.     *temp = '\0';
  356.     prog++;
  357.     return (token_type = BLOCK);
  358.   }
  359.   /* look for comments */
  360.   if(*prog=='/')
  361.     if(*(prog+1)=='*') { /* is a comment */
  362.       prog += 2;
  363.       do { /* find end of comment */
  364.         while(*prog!='*') prog++;
  365.         prog++;
  366.       } while (*prog!='/');
  367.       prog++;
  368.     }
  369.   if(strchr("!<>=", *prog)) { /* is or might be
  370.                   a relation operator */
  371.     switch(*prog) {
  372.       case '=':
  373.         if(*(prog+1)=='=') {
  374.       prog++; prog++;
  375.           *temp = EQ;
  376.           temp++; *temp = EQ; temp++;
  377.       *temp = '\0';
  378.       }
  379.     break;
  380.       case '!':
  381.         if(*(prog+1)=='=') {
  382.       prog++; prog++;
  383.           *temp = NE;
  384.           temp++; *temp = NE; temp++;
  385.       *temp = '\0';
  386.     }
  387.     break;
  388.       case '<':
  389.         if(*(prog+1)=='=') {
  390.       prog++; prog++;
  391.           *temp = LE; temp++; *temp = LE;
  392.         } else {
  393.       prog++;
  394.       *temp = LT;
  395.     }
  396.         temp++;
  397.     *temp = '\0';
  398.     break;
  399.       case '>':
  400.         if(*(prog+1)=='=') {
  401.       prog++; prog++;
  402.           *temp = GE; temp++; *temp = GE;
  403.         } else {
  404.       prog++;
  405.       *temp = GT;
  406.     }
  407.         temp++;
  408.     *temp = '\0';
  409.     break;
  410.     }
  411.     if(*token) return(token_type = DELIMITER);
  412.   }
  413.   if(strchr("+-*^/%=;(),'", *prog)){ /* delimiter */
  414.     *temp = *prog;
  415.     prog++; /* advance to next position */
  416.     temp++;
  417.     *temp = '\0'; 
  418.     return (token_type=DELIMITER);
  419.   }
  420.   if(*prog=='"') { /* quoted string */
  421.     prog++;
  422.     while(*prog!='"'&& *prog!='\r') *temp++ = *prog++;
  423.     if(*prog=='\r') sntx_err(SYNTAX);
  424.     prog++; *temp = '\0';
  425.     return(token_type=STRING);
  426.   }
  427.   if(isdigit(*prog)) { /* number */
  428.     while(!isdelim(*prog)) *temp++ = *prog++;
  429.     *temp = '\0';
  430.     return(token_type = NUMBER);
  431.   }
  432.   if(isalpha(*prog)) { /* var or command */
  433.     while(!isdelim(*prog)) *temp++ = *prog++;
  434.     token_type=TEMP;
  435.   }
  436.   *temp = '\0';
  437.   /* see if a string is a command or a variable */
  438.   if(token_type==TEMP) {
  439.     tok = look_up(token); /* convert to internal rep */
  440.     if(tok) token_type = KEYWORD; /* is a keyword */
  441.     else token_type = IDENTIFIER;
  442.   }
  443.   return token_type;
  444. }
  445.  
  446. /* Return a token to input stream. */
  447. void putback(void) 
  448. {
  449.   char *t; 
  450.   t = token; 
  451.   for(; *t; t++) prog--; 
  452. }
  453.  
  454. /* Look up a token's internal representation in the
  455.    token table.
  456. */
  457. look_up(char *s)
  458. {
  459.   register int i;
  460.   char *p;
  461.   /* convert to lowercase */
  462.   p = s;
  463.   while(*p){ *p = tolower(*p); p++; }
  464.   /* see if token is in table */
  465.   for(i=0; *table[i].command; i++)
  466.       if(!strcmp(table[i].command, s)) return table[i].tok;
  467.   return 0; /* unknown command */
  468. }
  469.  
  470. /* Return index of internal library function or -1 if
  471.    not found. */
  472. internal_func(char *s)
  473. {
  474.   int i;
  475.   for(i=0; intern_func[i].f_name[0]; i++) {
  476.     if(!strcmp(intern_func[i].f_name, s))  return i;
  477.   }
  478.   return -1;
  479. }
  480.  
  481. /* Return true if c is a delimiter. */
  482. isdelim(char c)
  483. {
  484.   if(strchr(" !;,+-<>'/*%^=()", c) || c==9 || c=='\r' || c==0) return 1;
  485.   return 0; 
  486. }
  487.  
  488. /* Return 1 if c is space or tab. */
  489. iswhite(char c)
  490. {
  491.   if(c==' ' || c=='\t')
  492.     return 1;
  493.   else
  494.     return 0;
  495. }
  496.